package other._1;

import java.util.*;

/*
 *   分治法求凸包
 */
public class QuickBull {
    List<Line> lines = new ArrayList<>();//点集pts的凸包

    //求凸包，结果存入lines中
    public List<Line> handle(List<Point> pts) {
        lines.clear();
        if (pts == null || pts.isEmpty()) {
            return lines;
        }
        List<Point> ptsLeft = new ArrayList<>();//左凸包中的点
        List<Point> ptsRight = new ArrayList<>();//右凸包中的点
        //按x坐标对pts排序
        pts.sort((p1, p2) -> Integer.compare(p1.x - p2.x, 0));
        Point p1 = pts.get(0);//最左边的点
        Point p2 = pts.get(pts.size() - 1);//最右边的点,用直线p1p2将原凸包分成两个小凸包
        Point p3;
        double area;
        for (int i = 1; i < pts.size(); i++) {//穷举所有的点
            p3 = pts.get(i);
            area = getArea(p1, p2, p3);//求此三点所成三角形的有向面积
            if      (area > 0)  ptsLeft.add(p3);//p3属于上
            else if (area < 0)  ptsRight.add(p3);//p3属于下
        }
        //分治求解
        d(p1, p2, ptsLeft);
        d(p2, p1, ptsRight);
        return lines;
    }

    private void d(Point p1, Point p2, List<Point> s) {
        //s集合为空
        if (s.isEmpty()) {
            lines.add(new Line(p1, p2));
            return;
        }
        //s集合不为空，寻找Pmax
        double area;
        double maxArea = 0;
        Point pMax = null;
        for (Point point : s) {
            area = getArea(p1, p2, point);//最大面积对应的点就是Pmax
            if (area > maxArea) {
                pMax = point;
                maxArea = area;
            }
        }
        //找出位于(p1, pMax)直线上方的点集s1
        //找出位于(pMax, p2)直线上方的点集s2
        List<Point> s1 = new ArrayList<>();
        List<Point> s2 = new ArrayList<>();
        for (Point p3 : s) {
            if      (getArea(p1, pMax, p3) > 0) s1.add(p3);
            else if (getArea(pMax, p2, p3) > 0) s2.add(p3);
        }
        //递归
        d(p1, pMax, s1);
        d(pMax, p2, s2);
    }

    // 当且仅当点p3位于直线(p1, p2)左侧时，表达式的符号为正 v✖w 逆时针 正 即w在v的上面
    private double getArea(Point p1, Point p2, Point p3) {
        // 三角形的面积等于返回值绝对值的二分之一
        return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p1.y * p2.x - p2.y * p3.x - p3.y * p1.x;
    }
}